import java.util.Objects;

public class HashBucket<K,V> {
    static class Node<K,V>{
        private K key;
        private V value;
        Node next;

        public Node(K key,V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?, ?> node = (Node<?, ?>) o;
            return Objects.equals(key, node.key) && Objects.equals(value, node.value) && Objects.equals(next, node.next);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    //定义一个Node数组
    public Node[] array;

    //哈希表中实际存储的元素个数
    public int usedSize;

    //负载因子
    public static final double factor = 0.75;

    //构造方法
    //初始化哈希表的长度为10,采用拉链法处理哈希冲突
    public HashBucket() {
        array = new Node[10];
    }

    //插入键值对
    public void insert(K key,V value) {

        if(key == null) {
            throw new NullPointerException("key is null");
        }
        //构建一个新的结点
        Node newNode = new Node(key,value);

        //计算结点的哈希地址
        int index = key.hashCode() % array.length;

        //查看计算出的哈希地址中有没有相同的元素，有的话则退出。没有的话则执行插入操作
        //cur指向计算出的哈希地址的头结点
        //curPrev指向cur的前一个结点
        Node cur = array[index];
        Node curPrev = null;

        if(cur == null) {
            array[index] = newNode;
            this.usedSize++;
            if(doFactor() >= 0.75) {
                grow();
            }
            return;
        }

        while(cur != null) {
            if(cur.key.equals(newNode.key)) {
                cur.value = newNode.value;
                return;
            }
            curPrev = cur;
            cur = cur.next;
        }

        //代码走到这里，说明计算出的哈希地址中没有和newNode.key相同的元素
        //执行插入操作，利用尾插法进行插入
        if(curPrev != null) {
            newNode.next = curPrev.next;
            curPrev.next = newNode;
        }else {
            newNode.next = cur.next;
            cur.next = newNode;
        }

        this.usedSize++;

        //计算装填因子，如果大于factor则扩容
        if(doFactor() >= 0.75) {
            grow();
        }
    }

    public double doFactor() {
        return this.usedSize*1.0/ array.length;
    }

    //当装填因子大于额定值factor的时候,对哈希表进行扩容。扩容之后需要重新哈希
    public void grow() {
        //构造一个是原来数组两倍长度的新数组
        Node[] newArray = new Node[2*this.array.length];

        //遍历原来的数组,将数组中的元素进行重新哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null) {
                //重新哈希,确认当前结点在新的哈希表中的位置
                int newIndex = cur.getKey().hashCode() % newArray.length;
                //采用尾插法将当前结点插入到新的哈希表中
                //newCur指向经过哈希函数计算出的新哈希表中的哈希地址
                //newParent指向newCur的前一个结点
                Node newCur = newArray[newIndex];
                Node newParent = null;
                if(newCur == null) {
                    newArray[newIndex] = cur;
                    cur = cur.next;
                    continue;
                }

                while(newCur != null) {
                    newParent = newCur;
                    newCur = newCur.next;
                }

                //代码走到这里，如果newParent不为空，则newParent指向newArray[newIndex]的最后一个结点
                //执行尾插法
                if(newParent != null) {
                    cur.next = newParent.next;
                    newParent.next = cur;
                }else {
                    cur.next = newCur.next;
                    newCur.next = cur;
                }
                cur = cur.next;
            }
        }

        //用新的数组替代旧的数组
        this.array = newArray;

    }

    //根据key来查找value
    public Object find(K key) {
        int index = key.hashCode() % this.array.length;
        Node cur = array[index];

        while(cur != null) {

            if(cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }

        //代码走到这里还没有结束，说明没有找到，直接返回null
        return null;
    }

    //在哈希表中删除指定的值
    public void delete(K key) {
        int index = key.hashCode() % array.length;
        Node cur = array[index];
        Node curPrev = null;

        if(cur == null) {
            return;
        }

        //判断链表的头结点是不是需要删除的结点
        if(cur.key.equals(key)) {
            //删除头结点
            array[index] = cur.next;
            this.usedSize--;
            return;
        }

        while(cur != null) {
            if(cur.key.equals(key)) {
                //开始执行删除操作
                curPrev.next = cur.next;
                this.usedSize--;
            }
            curPrev = cur;
            cur = cur.next;

        }

        //代码走到这里，说明哈希表中没有key
        //就不用执行删除操作
    }

}
